Example dataset

Let’s assume that we have 5 datapoints (“A”, “B”, “C”, “D”, “E”) embedded in 3-dimensional space. Our objective is to embed these points in the 2-dimensional space so that the local structure is preserved.

Step 1 - calculate the distances between points

Firstly we calculate the euclidean distances between the points in the high-dimensional space, i.e.:

$$d(x,y) = \sqrt{ \sum_{i=1}^{n} (x_{i} - y_{i})^{2} }$$

Step 2 - calculate the probability distribution in high-dim space

For each point in our dataset we calculate the similarity to other points, which is described in the original paper as follows: similarity of datapoint $x_{j}$ to datapoint $x_{i}$ is the conditional probability $p_{j|i}$ that $x_{i}$ would pick $x_{j}$ as its neighbor. Note that definition is not symmetric, i.e. $p_{j|i} \neq p_{i|j}$.

Let’s pick one point, e.g. “A” and calculate the aforementioned conditional probabilities with respect to point “A”:

We map the distances to the Gaussian distribution with mean = 0. The probabilities that point “A” will pick the point “B” as its neighbor is equal to the value of density of normal distribution $(0, \sigma_{A})$ in point “Dist A-B”:

Additionally, we assume that $p_{i|i} = 0$ by definition. After we calculate the densities for all points, we normalize the values in order to have the probability distribution. Overall, the probability that point $i$ will pick point $j$ is given by the formula:

$$p_{j|i} := \frac{exp(-|| x_{i} - x_{j} ||^{2} /2 \sigma_{i}^{2} )}{\sum_{k \neq i} exp(-|| x_{i} - x_{k} ||^{2} /2 \sigma_{i}^{2} )}$$

The remaining issue is the algorithm of determining the sigma values in the normal distribution (c.f. Appendix 1).

Now, we have the similarity of datapoint “A” to other datapoints defined as the conditional probability $p_{A|X}$ ($A$ would pick $X$ as it neighbor):

$P_{A}:$
$p_{B|A} = 0.302$
$p_{C|A} = 0.282$
$p_{D|A} = 0.189$
$p_{E|A} = 0.226$

Let’s calculate all 5 distributions (one distribition per one datapoint):

Step 3 - calculate probability distribution in low-dim space

Let’s do exactly the same thing in low-dimensional space by performing the following steps:

• we randomly select the coordinates of all datapoints in low-dimensional space
• instead of normal distribution we apply t-student distribution

Overall, the probability, that point i will pick point j is given by the formula:

$$q_{j|i} := \frac{exp(-|| x_{i} - x_{j} ||^{2})}{\sum_{k \neq i} exp(-|| x_{i} - x_{k} ||^{2} )}$$

Step 4 - train like a supervised model

Now, for each point we have two distributions: in low-dim space (Q) and high-dim space (P).

Now, the idea is to change to coordinates in low-dim space so that the $Q_{i}$ distributions are similar to the $P_{i}$ ones so that we can reflect the local structures of high-dim space in low-dim space. Effectively, we tackle the problem of finding optimizing the parameters (just like in supervised model):

• Parameters to be trained: coordinates of points in low-dimensional space
• Actual values: P-distributions
• Optimizer: stochastic gradient descent
• Loss function: Kullback–Leibler divergence:

$$D_{KL} (P || Q) = \sum_{x \in X} P(x) \cdot log_{2}\frac{P(x)}{Q(x)}$$

or, using the previous notations (for point A):

$$D_{KL} (P || Q) = \sum_{j \in \{B, C, D, E \}} p_{j|A} \cdot log_{2}\frac{p_{j|A}}{q_{j|A}}$$

For all points in the dataset:

$$D_{KL} (P || Q) = \sum_{i \in \{A, B, C, D, E \}} \sum_{j \in \{A, B, C, D, E \}} p_{j|i} \cdot log_{2}\frac{p_{j|i}}{q_{j|i}}$$

In practise, we can also define $p_{ij}:=\frac{p_{j|i} + p_{i|j}}{2n}$ and change the loss function to the folowing form:

$$D_{KL} (P || Q) = \sum_{i \in \{A, B, C, D, E \}} \sum_{j \in \{A, B, C, D, E \}} p_{ji} \cdot log_{2}\frac{p_{ji}}{q_{ji}},$$

where $p_{ij} = p_{ji}$ and $q_{ij} = q_{ji}$.

Final output

From technical reasons the original dataset was extended by adding some noise.

The results in 2-dim space are the following:

Iris

MNIST